from numpy import *
from .misc import *

def euclidean(x, ys):
    # distance = sqrt((x-x0)^2 + (x-x1)^2 + ... )
   
    return sqrt(sum((x - ys)**2, axis=1))


class KNearestNeighbor:
    def __init__(self, k=3, distance=euclidean):
        (self.k, self.distance) = (k, distance)
        pass

    def train(self, props, labels, params={}):
        (self.props, self.ranges, self.min_values) = normalize(props) if params.get("norm", True) else (props*1.0, 1, 0)
        self.labels = labels.copy()
        self.tree = params.get("tree", None)
        if self.tree:
            self.tree.create(self.props)

    def classify(self, xs):
        ys = []
        for x in (xs - self.min_values) / self.ranges:
            ys.append(sort_dict(frequency(self.__get_neighbors(x)), False, False)[0][0])

        return ys


    def __get_neighbors(self, x):
        '''获取k个最接近的点'''
        
        if self.tree:
            nearests = self.tree.find_nearest_neighbors(x, self.k)
            return [self.labels[item[1]] for item in nearests]
        else:
            distances = self.distance(x, self.props)

            sorted_distances = distances.argsort()
            return [self.labels[sorted_distances[i]] for i in range(self.k) ]


